package util;

public class Prime {

	/**
	 * 得到下一个素数
	 */
	public static int getNextPrime(int x) {
		for (int i = x + 1;; i++) {
			if (isPrime(i)) {
				return i;
			}
		}
	}

	/**
	 * 判断是否是素数
	 */
	public static boolean isPrime(int x) {
		if (x <= 0) {
			System.err.println("您输入的数据有误");
			return false;
		}
		// 1不是素数
		if (x == 1) {
			return false;
		}
		// 这个对于2以上的才有效
		int sqrtOfX = (int) Math.floor(Math.sqrt(x));
		for (int i = 2; i <= sqrtOfX; i++) {
			// 一旦有除尽的，就返回假
			if (x % i == 0) {
				return false;
			}
		}
		return true;
	}
	
	/**
	 * 返回其中的一个因子,为1代表是素数
	 * @return
	 */
	public static int getFactor(int x) {
		if (x <= 0) {
			System.err.println("您输入的数据有误");
			return -1;
		}
		// 1不是素数
		if (x == 1) {
			return 1;
		}
		// 这个对于2以上的才有效
		int sqrtOfX = (int) Math.floor(Math.sqrt(x));
		for (int i = 2; i <= sqrtOfX; i++) {
			// 一旦有除尽的，就返回假
			if (x % i == 0) {
				return i;
			}
		}
		return 1;
	}
	/**
	 * 小于n的素数的总数
	 * 参考：https://leetcode.com/problems/count-primes/#/description
	 */
	public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        for(int i = 2; i < n; i++){
            isPrime[i] = true;
        }
        // Loop's ending condition is i * i < n instead of i < sqrt(n)
        // to avoid repeatedly calling an expensive function sqrt().
        for (int i = 2; i * i < n; i++) {
        	//从2开始，逐渐去掉素数的倍数，比如去掉4 6 8 10...
        	//如果不是素数，比如4，那么去掉2的时候肯定包含了4的倍数，所以直接跳过即可
        	if (!isPrime[i]) continue;
        	//为什么可以从i * i开始呢，比如去3的倍数时，3 * 2 = 6肯定已经去掉了
        	//所以可以直接从i * i开始，然后是i * i + i;
        	for (int j = i * i; j < n; j += i) {
                isPrime[j] = false;
             }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
			if(isPrime[i]){
				count++;
			}
		}
        return count;
    }
}
